1. Field of the Invention
The present invention relates generally to compression and decompression of digitized image data used, for example, to represent text, graphics and scanned images. More particularly, the invention relates to encoding variant color image data during compression of the image data.
2. State of the Art
Digitized images displayed on scanners, monitors and printers are typically quantized on a pixel-by-pixel basis and stored in memory as pixel maps, more commonly referred to as pixmaps. A pixmap is a two-dimensional array of picture elements mapped to locations of the digitized image.
To provide sufficient color range and fidelity, each pixel is typically stored in memory as a set of color coordinates which define the pixel's color location in a given color space. For example, a pixel is typically represented by its red, green and blue color component values, or by its cyan, magenta and yellow color component values. The fidelity of the color reproduction is a function of the accuracy with which each color component is represented.
Due to the increased volume of data required to represent color images, effort has been directed to compression of color data pixmaps. Because it is not practical or possible to provide a digital representation for all possible colors, the data used to represent each color component is necessarily compromised. Color fidelity is further compromised when the data used to represent the various colors of an image is compressed.
Early attempts at image compression relied upon techniques deemed suitable for non-scanned image data (such as text and synthetic graphics), assuming that they would work equally well for scanned images. One such technique was run-length coding, as described in "Inside Macintosh, Volumes I, II, III", Addison-Wesley, Reading, Mass., 1985, ISBN 0-201-177374. Run-length compression exploits the repetition of pixel values in long data "runs" by transmitting a single pixel value together with the length of the "run". Such techniques are relatively simple and effective for data used to represent text and line-art. However, run-length coding techniques have proven less suitable for scanned images (such as scanned photographs or video images) where numerous colors typically exist.
More advanced compression techniques are directed to maintaining color as close to full fidelity as possible. However, these techniques are theoretically "lossy" in that information content (such as edge acuity of text included in the image) is not maintained.
Known efforts for compressing image data have addressed this drawback of compression techniques by segregating the data of a pixmap into two components: (1) scanned image components and (2) all remaining components (such as text and synthetic graphics). Once segregated, the scanned image components are passed through compression techniques better suited for compressing scanned images (such as the JPEG industry standard compression techniques). The remaining components of the image data are separately passed to compression techniques better suited for objects that require good edge acuity (such as run length encoding).
However, this technique of segregating image data components suffers significant drawbacks. One such drawback is that the function of segregating presents problems. Objects included within the image data have to be tagged as scanned image data or as non-scanned image data before being placed into the pixmap. Otherwise, there is no way of determining the type of object to which a pixel belongs. Additional complexities result when overlapping areas of scanned images and non-scanned images are included within the image data.
Accordingly, it would be desirable to provide a technique for compressing image data without requiring the complexities associated with segregating the image data into its scanned and non-scanned components. It would further be desirable to reduce any perceptible degradation of the decompressed image, regardless of whether the image data includes scanned images, non-scanned images or any combination thereof. For variable color images (that is, images which include two or more different colors or grey scale levels), it would be desirable to accurately encode the colors in a manner suitable for achieving high compression ratios without sacrificing color fidelity as perceived by the unaided eye when the compressed color variant image data is decompressed.
For color images, high compression ratios can only be achieved if the vast number of colors (including grey scale values) extant in the world are represented with a substantially reduced color palette. However, no known techniques have successfully achieved such a reduction without a substantial sacrifice of color fidelity. This lack of color fidelity is aggravated when attempts are made to compress both scanned and unscanned images collectively, without the benefit of segregation. That is, compressed digital data formats which are chosen to preserve the edge acuity of non-scanned images thereby reduce the number of data bits available to preserve color fidelity unless the width of the compressed data word used to represent each pixel, and/or overall memory size, is substantially increased. This lack of color fidelity is further aggravated when real-time compression of an incoming data stream is required. In the past, constraints associated with real-time compression have required the use of a severely limited color palette to reduce processing time.
Thus, it would be desirable to provide a technique for compressing image data which does not impose large memory requirements, and which does not sacrifice color fidelity when the data is decompressed, even when: (1) scanned and unscanned image data is compressed collectively; and (2) the image data is compressed in real-time.